package com.example.demo.arithmetic.algorithm.dynamic_programing;

// 动态规划 求出第n个斐波那契数列
// 要点
// 1.从已知问题解，推导出当前问题的解
// 2.推倒过程可以表达为一个数学公式
// 3.用一维数组 或者二维数组 来保存之前的计算结果（进一步优化）
public class Fibonacci {
    public static void main(String[] args) {
        // 前十个斐波那契数：
        //0 1 1 2 3 5 8 13 21 34
        int fibo = fibo(4);
        int fibo2 = fibo2(13);
        System.out.println(fibo);
        System.out.println(fibo2);
    }

    public static int fibo(int n) {
        // 已知的存到数组
        int[] arr = new int[n + 1];
        // 已知的解
        if (n == 0) {
            return 0;
        }
        arr[0] = 0;
        if (n == 1) {
            return 1;
        }
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

    /**
     * 降维 二维数组==>一维数组==>几个变量
     *
     * @param n
     * @return
     */
    public static int fibo2(int n) {
        // 已知的存到数组
        // 已知的解
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int a = 0;
        int b = 1;
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}
